package com.berchen.算法;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;

/**
 * 插入排序
 * 第一轮 将第一个元素当成是一个有序列表 然后将第二个元素和前面的有序列表进行比较 找到插入的位置 进行插入
 * 第二轮 将前面两个元素当成是一个有序列表 然后将第三个元素和前面的有序列表进行比较 找到插入的位置 进行插入
 * 第三轮 将前面三个元素当成是一个有序列表 然后将第四个元素和前面的有序列表进行比较 找到插入的位置 进行插入
 *
 * 。。。 以此类推
 *
 * 插入排序的问题？
 *  如果从小到大排序  如果要插入的数据非常小 比有序列表的所有数据都小 那么移动的数据非常多  影响效率
 *  如果从大到小排序 如果要插入的数据非常大 比有序列表的所有数据都大  那么移动的数据非常多  影响效率
 *
 * 如何解决这个问题？我们提出了 希尔排序。
 */
public class InsertSort {
    public static void main(String[] args) {

        int size=80000;
        int[] testArr=new int[size];
        for(int i =0;i<testArr.length;i++){
            testArr[i]=(int)(Math.random()*size);
        }

        Instant start=Instant.now();
        insertSort(testArr);
        Instant end=Instant.now();
        System.out.println(Duration.between(start,end).toMillis()); //801

//        System.out.println(Arrays.toString(testArr));

    }

    /**
     * 插入排序
     * @param arr
     */
    public static void insertSort(int[] arr){

        // 一共 n-1 轮
        for(int i =1;i<arr.length;i++){
            int insertValue=arr[i]; // 待排序的一个元素 i之前的数据都是有序的了
            int insertIndex=i-1;    // 待排序元素的插入位置
            /**
             * insertIndex>=0 保证索引不越界
             * insertValue<arr[insertIndex] 还没有找到要插入的位置
             */
            while (insertIndex>=0&&insertValue<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];    // 将数据往后移动  给待插入数据腾位置
                insertIndex--;
            }
            arr[insertIndex+1]=insertValue; // 将待插入的数据 插入到该插入的位置
        }
    }
}
